SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Karger's algorithm</title>

</head>

Karger's algorithm

</h1>

</header>

In <a href="Computer_science" title="Computer science">computer science</a> and <a href="Graph_theory" title="Graph theory">graph theory</a>, Karger's algorithm is a <a href="Randomized_algorithm" title="Randomized algorithm">randomized algorithm</a> to compute a <a href="Minimum_cut" title="Minimum cut">minimum cut</a> of a connected <a href="Graph_(discrete_mathematics)" title="Graph (discrete mathematics)">graph</a>. It was invented by <a href="David_Karger" title="David Karger">David Karger</a> and first published in 1993.<a href="#cite_note-karger1993-1">[1]</a>

The idea of the algorithm is based on the concept of <a href="Edge_contraction" title="Edge contraction">contraction of an edge</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (u,v)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (u,v)}</annotation>

</semantics>

</math><img src="./eadf12294edccd7a29c99cfc1765e4a14bf47e58.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.301ex; height:2.843ex;" alt="{\displaystyle (u,v)}" loading="lazy"> in an undirected graph <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G=(V,E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G=(V,E)}</annotation>

</semantics>

</math><img src="./644a8d85ee410b6159ca2bdb5dcb9097e2c8f182.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.331ex; height:2.843ex;" alt="{\displaystyle G=(V,E)}" loading="lazy">. Informally speaking, the contraction of an edge merges the nodes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u}</annotation>

</semantics>

</math><img src="./c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"> into one, reducing the total number of nodes of the graph by one. All other edges connecting either <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u}</annotation>

</semantics>

</math><img src="./c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}" loading="lazy"> or <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"> are "reattached" to the merged node, effectively producing a <a href="Multigraph" title="Multigraph">multigraph</a>. Karger's basic algorithm iteratively contracts randomly chosen edges until only two nodes remain; those nodes represent a <a href="Cut_(graph_theory)" title="Cut (graph theory)">cut</a> in the original graph. By iterating this basic algorithm a sufficient number of times, a minimum cut can be found <a href="With_high_probability" title="With high probability">with high probability</a>.

<div class="mw-heading mw-heading2"><h2 id="The_global_minimum_cut_problem">The global minimum cut problem</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Minimum_cut" title="Minimum cut">Minimum cut</a></div>

A cut <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (S,T)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (S,T)}</annotation>

</semantics>

</math><img src="./467faf91b93aed51e1dd1c656f1ae71d9c922a38.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.979ex; height:2.843ex;" alt="{\displaystyle (S,T)}" loading="lazy"> in an undirected graph <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G=(V,E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G=(V,E)}</annotation>

</semantics>

</math><img src="./644a8d85ee410b6159ca2bdb5dcb9097e2c8f182.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.331ex; height:2.843ex;" alt="{\displaystyle G=(V,E)}" loading="lazy"> is a partition of the vertices <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math><img src="./af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"> into two non-empty, disjoint sets <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\cup T=V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S\cup T=V}</annotation>

</semantics>

</math><img src="./12be003a91e8e260e6c297c26766b9580a9d2237.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:10.604ex; height:2.176ex;" alt="{\displaystyle S\cup T=V}" loading="lazy">. The cutset of a cut consists of the edges <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{\,uv\in E\colon u\in S,v\in T\,\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{\,uv\in E\colon u\in S,v\in T\,\}}</annotation>

</semantics>

</math><img src="./52bcfd364307a3df64c8fad6a5f442ad52d44090.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.515ex; height:2.843ex;" alt="{\displaystyle \{\,uv\in E\colon u\in S,v\in T\,\}}" loading="lazy"> between the two parts. The size (or weight) of a cut in an unweighted graph is the cardinality of the cutset, i.e., the number of edges between the two parts,

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w(S,T)=|\{\,uv\in E\colon u\in S,v\in T\,\}|\,.}</annotation>

</semantics>

</math><img src="./28274a8b13d8c876eb012040af98c6cecbf9208c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:36.584ex; height:2.843ex;" alt="{\displaystyle w(S,T)=|\{\,uv\in E\colon u\in S,v\in T\,\}|\,.}" loading="lazy"></dd></dl></dd></dl>

There are <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{|V|}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{|V|}}</annotation>

</semantics>

</math><img src="./c916bffe0b376bb83a0cc8513ddbe6e81ec2d169.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.573ex; height:2.843ex;" alt="{\displaystyle 2^{|V|}}" loading="lazy"> ways of choosing for each vertex whether it belongs to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> or to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math><img src="./ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy">, but two of these choices make <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> or <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math><img src="./ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy"> empty and do not give rise to cuts. Among the remaining choices, swapping the roles of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math><img src="./ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy"> does not change the cut, so each cut is counted twice; therefore, there are <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{|V|-1}-1}">

<msup>

</mrow>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{|V|-1}-1}</annotation>

</semantics>

</math><img src="./67fbaaddd44adfeff5e63669c77921684a45fb04.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:9.677ex; height:3.009ex;" alt="{\displaystyle 2^{|V|-1}-1}" loading="lazy"> distinct cuts.

The minimum cut problem is to find a cut of smallest size among these cuts.

For weighted graphs with positive edge weights <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w\colon E\rightarrow \mathbf {R} ^{+}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w\colon E\rightarrow \mathbf {R} ^{+}}</annotation>

</semantics>

</math><img src="./e2a97526976139fb9648063a5e34c28d67ff37aa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:11.602ex; height:2.509ex;" alt="{\displaystyle w\colon E\rightarrow \mathbf {R} ^{+}}" loading="lazy"> the weight of the cut is the sum of the weights of edges between vertices in each part

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w(S,T)=\sum _{uv\in E\colon u\in S,v\in T}w(uv)\,,}</annotation>

</semantics>

</math><img src="./edc8b8f3b77516818588b30357d49beccd883856.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:29.244ex; height:5.843ex;" alt="{\displaystyle w(S,T)=\sum _{uv\in E\colon u\in S,v\in T}w(uv)\,,}" loading="lazy"></dd></dl></dd></dl>

which agrees with the unweighted definition for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w=1}</annotation>

</semantics>

</math><img src="./19cbe03d2cb784a6fa6cd3727d4d2a71ed46fb74.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.925ex; height:2.176ex;" alt="{\displaystyle w=1}" loading="lazy">.

A cut is sometimes called a “global cut” to distinguish it from an “<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy">-<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"> cut” for a given pair of vertices, which has the additional requirement that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s\in S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s\in S}</annotation>

</semantics>

</math><img src="./acce52dffd84d073a24f4606a175da60148fd0c6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.43ex; height:2.176ex;" alt="{\displaystyle s\in S}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t\in T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t\in T}</annotation>

</semantics>

</math><img src="./b4fe93f70df3818ecca67c2ca44f087483951856.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.317ex; height:2.176ex;" alt="{\displaystyle t\in T}" loading="lazy">. Every global cut is an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy">-<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"> cut for some <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s,t\in V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s,t\in V}</annotation>

</semantics>

</math><img src="./9f1f09701bea7d83d020d74ffd3232663134d098.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.592ex; height:2.509ex;" alt="{\displaystyle s,t\in V}" loading="lazy">. Thus, the minimum cut problem can be solved in <a href="Polynomial_time" class="mw-redirect" title="Polynomial time">polynomial time</a> by iterating over all choices of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s,t\in V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s,t\in V}</annotation>

</semantics>

</math><img src="./9f1f09701bea7d83d020d74ffd3232663134d098.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.592ex; height:2.509ex;" alt="{\displaystyle s,t\in V}" loading="lazy"> and solving the resulting minimum <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy">-<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"> cut problem using the <a href="Max-flow_min-cut_theorem" title="Max-flow min-cut theorem">max-flow min-cut theorem</a> and a polynomial time algorithm for <a href="Maximum_flow" class="mw-redirect" title="Maximum flow">maximum flow</a>, such as the <a href="Push%E2%80%93relabel_maximum_flow_algorithm" title="Push–relabel maximum flow algorithm">push-relabel algorithm</a>, though this approach is not optimal. Better deterministic algorithms for the global minimum cut problem include the <a href="Stoer%E2%80%93Wagner_algorithm" title="Stoer–Wagner algorithm">Stoer–Wagner algorithm</a>, which has a running time of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(mn+n^{2}\log n)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(mn+n^{2}\log n)}</annotation>

</semantics>

</math><img src="./e6c65ba1ec52875d490e86d8eed282c87ce738a0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.448ex; height:3.176ex;" alt="{\displaystyle O(mn+n^{2}\log n)}" loading="lazy">.<a href="#cite_note-simplemincut-2">[2]</a>

<div class="mw-heading mw-heading2"><h2 id="Contraction_algorithm">Contraction algorithm</h2></div>

The fundamental operation of Karger’s algorithm is a form of <a href="Edge_contraction" title="Edge contraction">edge contraction</a>. The result of contracting the edge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e=\{u,v\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e=\{u,v\}}</annotation>

</semantics>

</math><img src="./6d3b64888aa50422dd9c27e44cb02bb1ff111999.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.998ex; height:2.843ex;" alt="{\displaystyle e=\{u,v\}}" loading="lazy"> is a new node <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle uv}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle uv}</annotation>

</semantics>

</math><img src="./4e6b4c628431f1c0bdf17baf5b94d2f46caa4c5f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.457ex; height:1.676ex;" alt="{\displaystyle uv}" loading="lazy">. Every edge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{w,u\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{w,u\}}</annotation>

</semantics>

</math><img src="./114d4cbc7806526db40fad5c82d4f9c18def8472.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.353ex; height:2.843ex;" alt="{\displaystyle \{w,u\}}" loading="lazy"> or <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{w,v\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{w,v\}}</annotation>

</semantics>

</math><img src="./2c5397818fc0e7546d5de98aefaf6800857bfb70.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.151ex; height:2.843ex;" alt="{\displaystyle \{w,v\}}" loading="lazy"> for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w\notin \{u,v\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w\notin \{u,v\}}</annotation>

</semantics>

</math><img src="./6f81a921c170b8129aec5d096e76ec697c2b0a39.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.321ex; height:2.843ex;" alt="{\displaystyle w\notin \{u,v\}}" loading="lazy"> to the endpoints of the contracted edge is replaced by an edge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{w,uv\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{w,uv\}}</annotation>

</semantics>

</math><img src="./3f3614b87f7e8fda22caada942b9937be5c34b68.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.48ex; height:2.843ex;" alt="{\displaystyle \{w,uv\}}" loading="lazy"> to the new node. Finally, the contracted nodes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u}</annotation>

</semantics>

</math><img src="./c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"> with all their incident edges are removed. In particular, the resulting graph contains no self-loops. The result of contracting edge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e}</annotation>

</semantics>

</math><img src="./cd253103f0876afc68ebead27a5aa9867d927467.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.083ex; height:1.676ex;" alt="{\displaystyle e}" loading="lazy"> is denoted <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G/e}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G/e}</annotation>

</semantics>

</math><img src="./0cd9d2447bfac511645f8b9ea6fa575ea1660308.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.073ex; height:2.843ex;" alt="{\displaystyle G/e}" loading="lazy">.

The contraction algorithm repeatedly contracts random edges in the graph, until only two nodes remain, at which point there is only a single cut.

The key idea of the algorithm is that it is far more likely for non min-cut edges than min-cut edges to be randomly selected and lost to contraction, since min-cut edges are usually vastly outnumbered by non min-cut edges. Subsequently, it is plausible that the min-cut edges will survive all the edge contraction, and the algorithm will correctly identify the min-cut edge.

<pre> procedure contract(<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G=(V,E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G=(V,E)}</annotation>

</semantics>

</math><img src="./644a8d85ee410b6159ca2bdb5dcb9097e2c8f182.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.331ex; height:2.843ex;" alt="{\displaystyle G=(V,E)}" loading="lazy">):

while <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |V|>2}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |V|>2}</annotation>

</semantics>

</math><img src="./854c0ae3c661b4d67c6214532e7e93349225f6b2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.342ex; height:2.843ex;" alt="{\displaystyle |V|>2}" loading="lazy">

choose <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e\in E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e\in E}</annotation>

</semantics>

</math><img src="./34778736d9c6d607a4da3d25594b38dd3e8c82ed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.7ex; height:2.176ex;" alt="{\displaystyle e\in E}" loading="lazy"> uniformly at random

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G\leftarrow G/e}</annotation>

</semantics>

</math><img src="./034a64c1a6929acec6392407d07477702ac71b45.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.513ex; height:2.843ex;" alt="{\displaystyle G\leftarrow G/e}" loading="lazy">

return the only cut in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy">

</pre>

When the graph is represented using <a href="Adjacency_list" title="Adjacency list">adjacency lists</a> or an <a href="Adjacency_matrix" title="Adjacency matrix">adjacency matrix</a>, a single edge contraction operation can be implemented with a linear number of updates to the data structure, for a total running time of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|V|^{2})}">

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|V|^{2})}</annotation>

</semantics>

</math><img src="./e1e99764e23be92b694aef042c6460ff921357e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.718ex; height:3.343ex;" alt="{\displaystyle O(|V|^{2})}" loading="lazy">. Alternatively, the procedure can be viewed as an execution of <a href="Kruskal%E2%80%99s_algorithm" class="mw-redirect" title="Kruskal’s algorithm">Kruskal’s algorithm</a> for constructing the <a href="Minimum_spanning_tree" title="Minimum spanning tree">minimum spanning tree</a> in a graph where the edges have weights <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w(e_{i})=\pi (i)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w(e_{i})=\pi (i)}</annotation>

</semantics>

</math><img src="./e15221f24cce03a0faeaf6c18e7bc0295ae52328.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.399ex; height:2.843ex;" alt="{\displaystyle w(e_{i})=\pi (i)}" loading="lazy"> according to a random permutation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \pi }</annotation>

</semantics>

</math><img src="./9be4ba0bb8df3af72e90a0535fabcc17431e540a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.332ex; height:1.676ex;" alt="{\displaystyle \pi }" loading="lazy">. Removing the heaviest edge of this tree results in two components that describe a cut. In this way, the contraction procedure can be implemented like <a href="Kruskal%E2%80%99s_algorithm" class="mw-redirect" title="Kruskal’s algorithm">Kruskal’s algorithm</a> in time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|E|\log |E|)}">

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|E|\log |E|)}</annotation>

</semantics>

</math><img src="./8a521bb148ab1e5e61317c713cbb88e65bd4b7bf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.467ex; height:2.843ex;" alt="{\displaystyle O(|E|\log |E|)}" loading="lazy">.

The best known implementations use <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|E|)}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|E|)}</annotation>

</semantics>

</math><img src="./976fe7f1e011d0dcdb3d6163754c877aaad5187f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.652ex; height:2.843ex;" alt="{\displaystyle O(|E|)}" loading="lazy"> time and space, or <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|E|\log |E|)}">

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|E|\log |E|)}</annotation>

</semantics>

</math><img src="./8a521bb148ab1e5e61317c713cbb88e65bd4b7bf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.467ex; height:2.843ex;" alt="{\displaystyle O(|E|\log |E|)}" loading="lazy"> time and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|V|)}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|V|)}</annotation>

</semantics>

</math><img src="./3486d00c2ed0f7eb1db550af8f239ad68241a6c5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.664ex; height:2.843ex;" alt="{\displaystyle O(|V|)}" loading="lazy"> space, respectively.<a href="#cite_note-karger1993-1">[1]</a>

<div class="mw-heading mw-heading3"><h3 id="Success_probability_of_the_contraction_algorithm">Success probability of the contraction algorithm</h3></div>

In a graph <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G=(V,E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G=(V,E)}</annotation>

</semantics>

</math><img src="./644a8d85ee410b6159ca2bdb5dcb9097e2c8f182.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.331ex; height:2.843ex;" alt="{\displaystyle G=(V,E)}" loading="lazy"> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=|V|}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=|V|}</annotation>

</semantics>

</math><img src="./8211dc5b1fcb14b6945b7163c2b9239b02066547.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.574ex; height:2.843ex;" alt="{\displaystyle n=|V|}" loading="lazy"> vertices, the contraction algorithm returns a minimum cut with polynomially small probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\binom {n}{2}}^{-1}}">

<msup>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\binom {n}{2}}^{-1}}</annotation>

</semantics>

</math><img src="./8f9511a776abbc05744eaa53dd66cbd403b27e53.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:7.149ex; height:6.509ex;" alt="{\displaystyle {\binom {n}{2}}^{-1}}" loading="lazy">. Recall that every graph has <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n-1}-1}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{n-1}-1}</annotation>

</semantics>

</math><img src="./e25a81c69b84a7d496ffe9821e199ae004ad260a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:8.484ex; height:2.843ex;" alt="{\displaystyle 2^{n-1}-1}" loading="lazy"> cuts (by the discussion in the previous section), among which at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tbinom {n}{2}}}">

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tbinom {n}{2}}}</annotation>

</semantics>

</math><img src="./bd5a9995ef7f68d5dd7d90d27c024615cf9fe4ec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.116ex; height:3.176ex;" alt="{\displaystyle {\tbinom {n}{2}}}" loading="lazy"> can be minimum cuts. Therefore, the success probability for this algorithm is much better than the probability for picking a cut at random, which is at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {\tbinom {n}{2}}{2^{n-1}-1}}}">

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {\tbinom {n}{2}}{2^{n-1}-1}}}</annotation>

</semantics>

</math><img src="./303dbc3f46af271ba74259de32a1494de08ac861.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:9.32ex; height:6.676ex;" alt="{\displaystyle {\frac {\tbinom {n}{2}}{2^{n-1}-1}}}" loading="lazy">.

For instance, the <a href="Cycle_graph" title="Cycle graph">cycle graph</a> on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> vertices has exactly <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\binom {n}{2}}}">

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\binom {n}{2}}}</annotation>

</semantics>

</math><img src="./5c2ec33f69a05fe8ccbd56bd287d84c93dfb7077.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:4.816ex; height:6.176ex;" alt="{\displaystyle {\binom {n}{2}}}" loading="lazy"> minimum cuts, given by every choice of 2 edges. The contraction procedure finds each of these with equal probability.

To further establish the lower bound on the success probability, let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> denote the edges of a specific minimum cut of size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">. The contraction algorithm returns <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> if none of the random edges deleted by the algorithm belongs to the cutset <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy">. In particular, the first edge contraction avoids <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy">, which happens with probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-k/|E|}">

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1-k/|E|}</annotation>

</semantics>

</math><img src="./2e94f4c86cde7241236e98540f00cdbf30493462.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.446ex; height:2.843ex;" alt="{\displaystyle 1-k/|E|}" loading="lazy">. The minimum <a href="Degree_(graph_theory)" title="Degree (graph theory)">degree</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> is at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> (otherwise a minimum degree vertex would induce a smaller cut where one of the two partitions contains only the minimum degree vertex), so <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |E|\geqslant nk/2}">

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |E|\geqslant nk/2}</annotation>

</semantics>

</math><img src="./badbeb164cbe80796f89fad5f326d05f072722a2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.099ex; height:2.843ex;" alt="{\displaystyle |E|\geqslant nk/2}" loading="lazy">. Thus, the probability that the contraction algorithm picks an edge from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> is

<mfrac>

<mrow>

</mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {k}{|E|}}\leqslant {\frac {k}{nk/2}}={\frac {2}{n}}.}</annotation>

</semantics>

</math><img src="./e6ba3a5a7f73370f43328c61eebe784ced155ee5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:18.747ex; height:6.176ex;" alt="{\displaystyle {\frac {k}{|E|}}\leqslant {\frac {k}{nk/2}}={\frac {2}{n}}.}" loading="lazy"></dd></dl></dd></dl></dd></dl></dd></dl>

The probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{n}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{n}}</annotation>

</semantics>

</math><img src="./6f79dcba35ecde0d43fbb7c914165586166ce8c2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.477ex; height:2.009ex;" alt="{\displaystyle p_{n}}" loading="lazy"> that the contraction algorithm on an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">-vertex graph avoids <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> satisfies the recurrence <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{n}\geqslant \left(1-{\frac {2}{n}}\right)p_{n-1}}">

<msub>

</mrow>

</msub>

<mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{n}\geqslant \left(1-{\frac {2}{n}}\right)p_{n-1}}</annotation>

</semantics>

</math><img src="./3f3b04c9662d3b423529240a24a1a0bee98e2f67.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; margin-left: -0.089ex; width:20.106ex; height:6.176ex;" alt="{\displaystyle p_{n}\geqslant \left(1-{\frac {2}{n}}\right)p_{n-1}}" loading="lazy">, with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{2}=1}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{2}=1}</annotation>

</semantics>

</math><img src="./2cc5b2ea9fb06b1cab43b930c90bfb58beeb5b60.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:6.574ex; height:2.509ex;" alt="{\displaystyle p_{2}=1}" loading="lazy">, which can be expanded as

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

</mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mrow>

</mrow>

</munderover>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

</mfrac>

</mrow>

<mfrac>

</mfrac>

</mrow>

<mfrac>

</mfrac>

</mrow>

<msup>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{n}\geqslant \prod _{i=0}^{n-3}{\Bigl (}1-{\frac {2}{n-i}}{\Bigr )}=\prod _{i=0}^{n-3}{\frac {n-i-2}{n-i}}={\frac {n-2}{n}}\cdot {\frac {n-3}{n-1}}\cdot {\frac {n-4}{n-2}}\cdots {\frac {3}{5}}\cdot {\frac {2}{4}}\cdot {\frac {1}{3}}={\binom {n}{2}}^{-1}\,.}</annotation>

</semantics>

</math><img src="./d424852e8f38afbfba7917f992b893ae2435b66b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; margin-left: -0.089ex; width:87.441ex; height:7.176ex;" alt="{\displaystyle p_{n}\geqslant \prod _{i=0}^{n-3}{\Bigl (}1-{\frac {2}{n-i}}{\Bigr )}=\prod _{i=0}^{n-3}{\frac {n-i-2}{n-i}}={\frac {n-2}{n}}\cdot {\frac {n-3}{n-1}}\cdot {\frac {n-4}{n-2}}\cdots {\frac {3}{5}}\cdot {\frac {2}{4}}\cdot {\frac {1}{3}}={\binom {n}{2}}^{-1}\,.}" loading="lazy"></dd></dl></dd></dl></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Repeating_the_contraction_algorithm">Repeating the contraction algorithm</h3></div>

By repeating the contraction algorithm <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T={\binom {n}{2}}\ln n}">

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T={\binom {n}{2}}\ln n}</annotation>

</semantics>

</math><img src="./715acbd0204487481aa29440a228cb0008d3253a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:13.659ex; height:6.176ex;" alt="{\displaystyle T={\binom {n}{2}}\ln n}" loading="lazy"> times with independent random choices and returning the smallest cut, the probability of not finding a minimum cut is

<msup>

<mrow>

<mrow>

<msup>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</msup>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left[1-{\binom {n}{2}}^{-1}\right]^{T}\leq {\frac {1}{e^{\ln n}}}={\frac {1}{n}}\,.}</annotation>

</semantics>

</math><img src="./6844af7b05ed88e23beb927dde041dafaff1a8a9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:29.609ex; height:8.009ex;" alt="{\displaystyle \left[1-{\binom {n}{2}}^{-1}\right]^{T}\leq {\frac {1}{e^{\ln n}}}={\frac {1}{n}}\,.}" loading="lazy"></dd></dl></dd></dl></dd></dl>

The total running time for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math><img src="./ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy"> repetitions for a graph with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> vertices and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> edges is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(Tm)=O(n^{2}m\log n)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(Tm)=O(n^{2}m\log n)}</annotation>

</semantics>

</math><img src="./1505050ba4d3798edf2b56217cc913d81a47c39e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.57ex; height:3.176ex;" alt="{\displaystyle O(Tm)=O(n^{2}m\log n)}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Karger–Stein_algorithm">Karger–Stein algorithm</h2></div>

An extension of Karger’s algorithm due to <a href="David_Karger" title="David Karger">David Karger</a> and <a href="Clifford_Stein" title="Clifford Stein">Clifford Stein</a> achieves an order of magnitude improvement.<a href="#cite_note-faster-3">[3]</a>

The basic idea is to perform the contraction procedure until the graph reaches <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"> vertices.

<pre> procedure contract(<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G=(V,E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G=(V,E)}</annotation>

</semantics>

</math><img src="./644a8d85ee410b6159ca2bdb5dcb9097e2c8f182.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.331ex; height:2.843ex;" alt="{\displaystyle G=(V,E)}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy">):

while <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |V|>t}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |V|>t}</annotation>

</semantics>

</math><img src="./f65d37960afb0a42f967af205ab066bf496f5560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.019ex; height:2.843ex;" alt="{\displaystyle |V|>t}" loading="lazy">

choose <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e\in E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e\in E}</annotation>

</semantics>

</math><img src="./34778736d9c6d607a4da3d25594b38dd3e8c82ed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.7ex; height:2.176ex;" alt="{\displaystyle e\in E}" loading="lazy"> uniformly at random

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G\leftarrow G/e}</annotation>

</semantics>

</math><img src="./034a64c1a6929acec6392407d07477702ac71b45.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.513ex; height:2.843ex;" alt="{\displaystyle G\leftarrow G/e}" loading="lazy">

return <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy">

</pre>

The probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{n,t}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{n,t}}</annotation>

</semantics>

</math><img src="./73ec7130acc2e187ac114bc1b9bd47981986f66f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; margin-left: -0.089ex; width:3.528ex; height:2.343ex;" alt="{\displaystyle p_{n,t}}" loading="lazy"> that this contraction procedure avoids a specific cut <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> in an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">-vertex graph is

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

</mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{n,t}\geq \prod _{i=0}^{n-t-1}{\Bigl (}1-{\frac {2}{n-i}}{\Bigr )}={\binom {t}{2}}{\Bigg /}{\binom {n}{2}}\,.}</annotation>

</semantics>

</math><img src="./affa8c3679d9a0719279fae6b003a0631640959e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; margin-left: -0.089ex; width:41.126ex; height:7.509ex;" alt="{\displaystyle p_{n,t}\geq \prod _{i=0}^{n-t-1}{\Bigl (}1-{\frac {2}{n-i}}{\Bigr )}={\binom {t}{2}}{\Bigg /}{\binom {n}{2}}\,.}" loading="lazy">

This expression is approximately <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t^{2}/n^{2}}">

<msup>

</mrow>

</msup>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t^{2}/n^{2}}</annotation>

</semantics>

</math><img src="./34b34ce797cf944621cbad45bcf871f028d0dd11.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.505ex; height:3.176ex;" alt="{\displaystyle t^{2}/n^{2}}" loading="lazy"> and becomes less than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {1}{2}}}">

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {1}{2}}}</annotation>

</semantics>

</math><img src="./a11cfb2fdb143693b1daf78fcb5c11a023cb1c55.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:1.999ex; height:5.176ex;" alt="{\displaystyle {\frac {1}{2}}}" loading="lazy"> around <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t=n/{\sqrt {2}}}">

</mrow>

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t=n/{\sqrt {2}}}</annotation>

</semantics>

</math><img src="./49a7cb426025b713b640b049fce196f48321888c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.594ex; height:3.176ex;" alt="{\displaystyle t=n/{\sqrt {2}}}" loading="lazy">. In particular, the probability that an edge from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> is contracted grows towards the end. This motivates the idea of switching to a slower algorithm after a certain number of contraction steps.

<pre> procedure fastmincut(<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G=(V,E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G=(V,E)}</annotation>

</semantics>

</math><img src="./644a8d85ee410b6159ca2bdb5dcb9097e2c8f182.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.331ex; height:2.843ex;" alt="{\displaystyle G=(V,E)}" loading="lazy">):

if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |V|\leq 6}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |V|\leq 6}</annotation>

</semantics>

</math><img src="./38e4d7bf15a10f9f4a23dfab557a26658be93a89.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.342ex; height:2.843ex;" alt="{\displaystyle |V|\leq 6}" loading="lazy">:

return contract(<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2}</annotation>

</semantics>

</math><img src="./901fc910c19990d0dbaaefe4726ceb1a4e217a0f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 2}" loading="lazy">)

else:

</mrow>

</mrow>

</mrow>

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t\leftarrow \lceil 1+|V|/{\sqrt {2}}\rceil }</annotation>

</semantics>

</math><img src="./15760a32055edf8d9270996f81b1d134325adac9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.863ex; height:3.176ex;" alt="{\displaystyle t\leftarrow \lceil 1+|V|/{\sqrt {2}}\rceil }" loading="lazy">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}\leftarrow }</annotation>

</semantics>

</math><img src="./9a695a1a596d1040b9841139acca1c4fb56f5144.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.85ex; height:2.509ex;" alt="{\displaystyle G_{1}\leftarrow }" loading="lazy"> contract(<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy">)

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{2}\leftarrow }</annotation>

</semantics>

</math><img src="./bcb8c4e8f8408164559e7af3b15303c8be6d97c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.85ex; height:2.509ex;" alt="{\displaystyle G_{2}\leftarrow }" loading="lazy"> contract(<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy">)

return min{fastmincut(<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}}</annotation>

</semantics>

</math><img src="./e6ea4f4668b8334c8a7d3d284b0fd22131ef5f52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{1}}" loading="lazy">), fastmincut(<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{2}}</annotation>

</semantics>

</math><img src="./645011b0c6933a02f5f7d84624f78220d747427e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{2}}" loading="lazy">)}

</pre>

<div class="mw-heading mw-heading3"><h3 id="Analysis">Analysis</h3></div>

The contraction parameter <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"> is chosen so that each call to contract has probability at least 1/2 of success (that is, of avoiding the contraction of an edge from a specific cutset <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy">). This allows the successful part of the recursion tree to be modeled as a <a href="Random_binary_tree" title="Random binary tree">random binary tree</a> generated by a critical <a href="Galton%E2%80%93Watson_process" title="Galton–Watson process">Galton–Watson process</a>, and to be analyzed accordingly.<a href="#cite_note-faster-3">[3]</a>

The probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(n)}</annotation>

</semantics>

</math><img src="./5e303d2c14cd399b6f52b468c9fd44a542bed422.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.949ex; height:2.843ex;" alt="{\displaystyle P(n)}" loading="lazy"> that this random tree of successful calls contains a long-enough path to reach the base of the recursion and find <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> is given by the recurrence relation

<msup>

<mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

<mrow>

<mrow>

</mrow>

<mfrac>

<msqrt>

</msqrt>

</mfrac>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(n)=1-\left(1-{\frac {1}{2}}P\left({\Bigl \lceil }1+{\frac {n}{\sqrt {2}}}{\Bigr \rceil }\right)\right)^{2}}</annotation>

</semantics>

</math><img src="./85cec48539e923f7db103f0d18215bbf98ee6dff.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.838ex; width:38.474ex; height:6.843ex;" alt="{\displaystyle P(n)=1-\left(1-{\frac {1}{2}}P\left({\Bigl \lceil }1+{\frac {n}{\sqrt {2}}}{\Bigr \rceil }\right)\right)^{2}}" loading="lazy"></dd></dl></dd></dl></dd></dl>

with solution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(n)=\Omega \left({\frac {1}{\log n}}\right)}">

<mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(n)=\Omega \left({\frac {1}{\log n}}\right)}</annotation>

</semantics>

</math><img src="./9f35c2d2de7a1b5a84e1d79e6a637924ac85bfd5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:19.124ex; height:6.176ex;" alt="{\displaystyle P(n)=\Omega \left({\frac {1}{\log n}}\right)}" loading="lazy">. The running time of fastmincut satisfies

<mrow>

<mrow>

</mrow>

<mfrac>

<msqrt>

</msqrt>

</mfrac>

</mrow>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T(n)=2T\left({\Bigl \lceil }1+{\frac {n}{\sqrt {2}}}{\Bigr \rceil }\right)+O(n^{2})}</annotation>

</semantics>

</math><img src="./9a784a76d5d56aad694c99d3b3c6837cbb8afe7e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.838ex; width:33.81ex; height:6.509ex;" alt="{\displaystyle T(n)=2T\left({\Bigl \lceil }1+{\frac {n}{\sqrt {2}}}{\Bigr \rceil }\right)+O(n^{2})}" loading="lazy"></dd></dl></dd></dl></dd></dl>

with solution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T(n)=O(n^{2}\log n)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T(n)=O(n^{2}\log n)}</annotation>

</semantics>

</math><img src="./b898d483445d6602ad4a5a296333fdac6611e912.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.111ex; height:3.176ex;" alt="{\displaystyle T(n)=O(n^{2}\log n)}" loading="lazy">. To achieve error probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1/n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(1/n)}</annotation>

</semantics>

</math><img src="./38260acab73dde5dabd2b2e6c48f0519d18b86cd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.302ex; height:2.843ex;" alt="{\displaystyle O(1/n)}" loading="lazy">, the algorithm can be repeated <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log n/P(n))}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log n/P(n))}</annotation>

</semantics>

</math><img src="./1c6156ec49e6e94c04a9e70147db039ec06e8d2a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.448ex; height:2.843ex;" alt="{\displaystyle O(\log n/P(n))}" loading="lazy"> times, for an overall running time of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T(n)\cdot {\frac {\log n}{P(n)}}=O(n^{2}\log ^{3}n)}">

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T(n)\cdot {\frac {\log n}{P(n)}}=O(n^{2}\log ^{3}n)}</annotation>

</semantics>

</math><img src="./88668fa346d3cf028bde0ae4efa17bf3f223ff33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:27.63ex; height:6.176ex;" alt="{\displaystyle T(n)\cdot {\frac {\log n}{P(n)}}=O(n^{2}\log ^{3}n)}" loading="lazy">. This is an order of magnitude improvement over Karger’s original algorithm.<a href="#cite_note-faster-3">[3]</a>

<div class="mw-heading mw-heading3"><h3 id="Improvement_bound">Improvement bound</h3></div>

To determine a min-cut, one has to touch every edge in the graph at least once, which is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta (n^{2})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n^{2})}</annotation>

</semantics>

</math><img src="./215877752c4f392a7276328d4d37709bf7c3f55d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.066ex; height:3.176ex;" alt="{\displaystyle \Theta (n^{2})}" loading="lazy"> time in a <a href="Dense_graph" title="Dense graph">dense graph</a>. The Karger–Stein's min-cut algorithm takes the running time of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{2}\ln ^{O(1)}n)}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{2}\ln ^{O(1)}n)}</annotation>

</semantics>

</math><img src="./b98934f105da5dd6733c49d3a35cce22049cdff5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.727ex; height:3.343ex;" alt="{\displaystyle O(n^{2}\ln ^{O(1)}n)}" loading="lazy">, which is very close to that.

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFKarger1993" class="citation conference cs1">Karger, David (1993). <a rel="nofollow" class="external text" href="http://people.csail.mit.edu/karger/Papers/mincut.ps">"Global Min-cuts in RNC and Other Ramifications of a Simple Mincut Algorithm"</a>. Proc. 4th Annual ACM-SIAM Symposium on Discrete Algorithms.</cite>

</li>

<li id="cite_note-simplemincut-2"><a href="#cite_ref-simplemincut_2-0">^</a> <cite id="CITEREFStoerWagner1997" class="citation journal cs1">Stoer, M.; Wagner, F. (1997). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F263867.263872">"A simple min-cut algorithm"</a>. Journal of the ACM. 44 (4): 585. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F263867.263872">10.1145/263867.263872</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:15220291">15220291</a>.</cite>

</li>

<li id="cite_note-faster-3">^ <a href="#cite_ref-faster_3-0">a</a> <a href="#cite_ref-faster_3-1">b</a> <a href="#cite_ref-faster_3-2">c</a> <cite id="CITEREFKargerStein1996" class="citation journal cs1"><a href="David_Karger" title="David Karger">Karger, David R.</a>; <a href="Clifford_Stein" title="Clifford Stein">Stein, Clifford</a> (1996). <a rel="nofollow" class="external text" href="http://www.columbia.edu/~cs2035/courses/ieor6614.S09/Contraction.pdf">"A new approach to the minimum cut problem"</a> (PDF). Journal of the ACM. 43 (4): 601. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F234533.234534">10.1145/234533.234534</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:5385337">5385337</a>.</cite>

</li>

</ol></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-03-17" href="https://en.wikipedia.org/wiki/?title=Karger's_algorithm&oldid=1280996450">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>